#include <bits/stdc++.h>
using namespace std;

/*
2322. 从树中删除边的最小分数
已解答
困难
相关标签
premium lock icon
相关企业
提示
存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点， 以及 n - 1 条边。

给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。

删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：

分别获取三个组件 每个 组件中所有节点值的异或值。
最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
例如，三个组件的节点值分别是：[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3 。最大异或值是 8 ，最小异或值是 3 ，分数是 8 - 3 = 5 。
返回在给定树上执行任意删除边方案可能的 最小 分数。

 

示例 1：


输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：9
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。
分数是最大异或值和最小异或值的差值，10 - 1 = 9 。
可以证明不存在分数比 9 小的删除边方案。
示例 2：


输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出：0
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。
分数是最大异或值和最小异或值的差值，0 - 0 = 0 。
无法获得比 0 更小的分数 0 。
 

提示：

n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树
*/

// 法一
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        // 构建邻接表表示树（无向图）
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        // 辅助数组：
        // parent[u]：节点u的父节点（用于确定树的方向）
        // size[u]：以u为根的子树大小（本题未直接使用，预处理保留）
        // in[u]/out[u]：节点u的进入/离开时间戳（用于判断子树包含关系）
        // xorSubTree[u]：以u为根的子树中所有节点的异或值
        vector<int> parent(n, -1), size(n, 1), in(n), out(n);
        vector<int> xorSubTree = nums;  // 初始化子树异或值为节点自身值
        int time = 0;  // 时间戳计数器

        // DFS预处理：计算子树异或值、时间戳、父节点等信息
        function<void(int)> dfs = [&](int u) {
            in[u] = time++;  // 记录进入时间（子树开始的时间）
            for (int v : adj[u]) {
                if (v != parent[u]) {  // 避免访问父节点（保证DFS方向）
                    parent[v] = u;     // 记录v的父节点为u
                    dfs(v);            // 递归处理子节点v
                    size[u] += size[v];  // 更新当前节点的子树大小
                    xorSubTree[u] ^= xorSubTree[v];  // 子树异或值 = 自身值 ^ 所有子节点的子树异或值
                }
            }
            out[u] = time - 1;  // 记录离开时间（子树结束的时间）
        };

        dfs(0);  // 从根节点0开始DFS

        int totalXor = xorSubTree[0];  // 整棵树的异或值（根节点的子树异或值）
        int minSco = INT_MAX;  // 记录最小分数（最大异或与最小异或的差值）

        // 枚举所有可能的两条边的组合（i < j 避免重复）
        for (int i = 0; i < edges.size(); i++) {
            int u1 = edges[i][0], v1 = edges[i][1];
            // 确保v1是u1的子节点（边的方向为u1->v1，v1在u1的子树中）
            // 若u1的父节点是v1，说明实际方向是v1->u1，交换后v1为子节点
            if (parent[u1] == v1) swap(u1, v1);

            for (int j = i + 1; j < edges.size(); j++) {
                int u2 = edges[j][0], v2 = edges[j][1];
                // 同理，确保v2是u2的子节点
                if (parent[u2] == v2) swap(u2, v2);

                int x, y, z;  // 三个组件的异或值
                // 判断v2是否在v1的子树中：子树的in时间在父树in之后，out时间在父树out之前
                bool isAncestor = in[v1] <= in[v2] && out[v1] >= out[v2];
                // 判断v1是否在v2的子树中（反向包含）
                bool isAncestorRev = in[v2] <= in[v1] && out[v2] >= out[v1];

                if (isAncestor) {
                    // 情况1：v2在v1的子树中
                    // x：v2子树的异或值
                    // y：v1子树中除去v2子树的部分（v1异或v2，因为v1包含v2）
                    // z：整棵树除去v1子树的部分（总异或异或v1）
                    x = xorSubTree[v2];
                    y = xorSubTree[v1] ^ x;
                    z = totalXor ^ xorSubTree[v1];
                } else if (isAncestorRev) {
                    // 情况2：v1在v2的子树中
                    // x：v1子树的异或值
                    // y：v2子树中除去v1子树的部分（v2异或v1）
                    // z：整棵树除去v2子树的部分（总异或异或v2）
                    x = xorSubTree[v1];
                    y = xorSubTree[v2] ^ x;
                    z = totalXor ^ xorSubTree[v2];
                } else {
                    // 情况3：v1和v2的子树不相交
                    // x：v1子树的异或值
                    // y：v2子树的异或值
                    // z：整棵树除去v1和v2子树的部分（总异或异或x异或y）
                    x = xorSubTree[v1];
                    y = xorSubTree[v2];
                    z = totalXor ^ x ^ y;
                }

                // 计算当前组合的分数（最大异或 - 最小异或）
                int minVal = min({x, y, z});
                int maxVal = max({x, y, z});
                minSco = min(minSco, maxVal - minVal);  // 更新最小分数
            }
        }

        return minSco;
    }
};

/**
 * 1. 数据结构设计
 * 字典树节点（node）：存储单一来源的异或值，支持插入、合并操作。每个节点包含：
 * 左子树（_l，当前位为 0）、右子树（_r，当前位为 1）；
 * 叶节点存储的异或值（v）、子树内异或值的最小值（min）和最大值（max）。
 * 组合字典树节点（node3）：整合三个不同来源的字典树节点（如父方向、前缀、后缀），支持同时查询多源异或信息。
 * 内存池（Pool、Pool3）：预分配节点内存，避免动态内存分配开销，提升效率。
 * 2. 预处理：四次 DFS 获取异或信息
 * 通过四次 DFS 分别计算树中不同方向的异或值，并构建对应的字典树，覆盖所有可能的组件分割方式。
 * （1）dfs1：子树内异或信息（t1字典树）
 * 计算以每个节点为根的子树的异或和（s_below[x]）；
 * 构建t1[x]：存储节点x的子树中所有子树的异或值（用于查询子树内的组件）。
 * （2）dfs2：父方向异或信息（t2字典树）
 * 计算从父节点到根的异或值（排除当前子树）；
 * 构建t2[x]：存储节点x父方向的异或值（用于查询父侧的组件）。
 * （3）dfs3：前缀异或信息（t3字典树）
 * 记录从根到当前节点的路径上的异或值；
 * 构建t3[x]：存储根到x的路径异或值（用于查询根侧的组件）。
 * （4）dfs4：后缀异或信息（t4字典树）
 * 记录从当前节点到叶节点的路径上的异或值；
 * 构建t4[x]：存储x到叶的路径异或值（用于查询叶侧的组件）。
 * 3. 核心查询：solve函数
 * 在字典树中查找最优异或组合，计算三个组件的异或值差值的最小值。函数分多种情况处理组件的不同分割方式：
 * （1）情况 1.1：((A,B),C)，C为有效组件
 * 枚举C的异或值，查询A和B的最优值，最小化max(A,B,C) - min(A,B,C)。
 * （2）情况 1.2：(A,(B,C))，A为有效组件
 * 枚举A的异或值，查询B和C的最优值，同样最小化差值。
 * （3）情况 1.3 & 1.4：A&B或B&C为有效组合
 * 针对A和B、B和C的组合，深入字典树查找最优值，进一步优化差值。
 * 4. 剪枝优化：lb函数
 * 计算当前查询的理论最小差值下界，若下界大于等于已有最优解，则跳过该查询，减少无效计算，提升效率。
 * 5. 主流程
 * 初始化树的邻接表，计算整棵树的总异或和（s）；
 * 执行四次预处理 DFS，构建t1、t2、t3、t4字典树；
 * 遍历所有节点，调用solve函数查询最优解，返回最小分数。
 */

// 法二  字典树
const int N = 1005, L = 27,
          inf = ~0u >> 2; // N:节点最大数量; L:二进制最高位(2^26); inf:无穷大值
struct node {             // 字典树节点结构(用于存储异或值)
    node *_l, *_r;        // _l:左子树(当前位为0); _r:右子树(当前位为1)
    int v, min, max;      // v:叶节点存储的异或值(非叶为-1);
                          // min/max:子树中异或值的最小/最大值
    node(node* _l = 0, node* _r = 0, int _min = inf, int _max = 0)
        : _l(_l), _r(_r), min(_min), max(_max), v(-1) {}
    node* l() { return _l; } // 返回左子节点
    node* r() { return _r; } // 返回右子节点
} Pool[N * L * 5], *p,
    *root; // Pool:node节点内存池; p:当前可用节点指针; root:临时根节点
node *t1[N], *t2[N], *t3[N],
    *t4[N]; // 存储不同方向的字典树: t1(子树内), t2(父方向), t3(前缀), t4(后缀)

// 创建新node节点(从内存池获取)
inline node* newnode(node* l = 0, node* r = 0, int x = -1) {
    p->_l = l;
    p->_r = r;
    if (x == -1) { // 非叶节点: 最值由子节点决定
        p->min = l ? l->min : (r ? r->min : inf);
        p->max = r ? r->max : (l ? l->max : 0);
        p->v = -1;
    } else { // 叶节点: 存储具体异或值, 最值为自身
        p->v = p->min = p->max = x;
    }
    return p++;
}

// 合并两个字典树(整合子树异或信息)
node* merge(node* x, node* y) {
    if (!x || !y)
        return x ? x : y; // 有一个为空则返回非空的
    // 递归合并左右子树
    return newnode(merge(x->_l, y->_l), merge(x->_r, y->_r), x->v);
}

// 向字典树插入异或值(从高位到低位插入)
node* insert(node* x, int key, int d = L - 1) {
    if (d < 0)
        return x ? x : newnode(0, 0, key); // 最低位: 新建叶节点存储值
    node *l = x ? x->_l : 0, *r = x ? x->_r : 0;
    // 根据当前位(第d位)决定插入左/右子树
    if ((key >> d) & 1)
        return newnode(l, insert(r, key, d - 1)); // 第d位为1: 插入右子树
    else
        return newnode(insert(l, key, d - 1), r); // 第d位为0: 插入左子树
}

// 调试用: 打印字典树(暂未使用)
// void print(node* x, int key = 0, int d = L) {
//     if (!x)
//         return;
//     if (!x->_l && !x->_r)
//         printf("%d %d d=%d\n", key, x->v, d);
//     else
//         print(x->_l, key * 2, d - 1), print(x->_r, key * 2 + 1, d - 1);
// }

// 计算字典树深度(暂未使用)
int D(node* x) { return !x ? -1 : max(D(x->_l), D(x->_r)) + 1; }

struct node3; // 前置声明: 组合三个字典树的节点
node3* newnode3(node* a0, node* a1, node* a2);

struct node3 {       // 组合字典树节点(同时管理三个来源的异或信息)
    node* a[3];      // 存储三个字典树节点(a0/a1/a2分别对应不同来源)
    int v, min, max; // 组合后的代表值、最小/最大值
    node3() {}
    node3(node* a0, node* a1, node* a2) { // 初始化: 合并三个子树的最值
        a[0] = a0;
        a[1] = a1;
        a[2] = a2;
        min = inf;
        max = 0;
        v = -1;
        if (a0)
            min = ::min(min, a0->min), max = ::max(max, a0->max), v = a0->v;
        if (a1)
            min = ::min(min, a1->min), max = ::max(max, a1->max), v = a1->v;
        if (a2)
            min = ::min(min, a2->min), max = ::max(max, a2->max), v = a2->v;
    }
    // 返回组合后的左子节点(整合三个子树的左子节点)
    node3* l() {
        return newnode3(a[0] ? a[0]->_l : 0, a[1] ? a[1]->_l : 0,
                        a[2] ? a[2]->_l : 0);
    }
    // 返回组合后的右子节点(整合三个子树的右子节点)
    node3* r() {
        return newnode3(a[0] ? a[0]->_r : 0, a[1] ? a[1]->_r : 0,
                        a[2] ? a[2]->_r : 0);
    }
} Pool3[N * L * 5], *p3; // Pool3:node3节点内存池; p3:当前可用节点指针

// 创建新node3节点(从内存池获取)
inline node3* newnode3(node* a0, node* a1, node* a2) {
    *p3 = node3(a0, a1, a2);
    return p3++;
}

// 判断节点是否存在(非空)
inline bool exist(node* x) { return x; }
inline bool exist(node3* x) { return x && (x->a[0] || x->a[1] || x->a[2]); }

// 获取x的第i位(0或1)
inline int get(int x, int i) { return (x >> i) & 1; }

// 获取x的最高有效位位置(如1010的最高位是3,即2^3)
inline int msb(int x) { return x ? 31 - __builtin_clz(x) : -1; }

// 全局变量:
int s_below[N];   // s_below[x]:以x为根的子树的异或和
int s;            // 整棵树的总异或和(所有节点异或结果)
int ans;          // 最终答案: 最小分数(最大异或-最小异或)
int* a;           // 指向输入的节点值数组
vector<int> e[N]; // 树的邻接表

class Solution {
public:
    // 第一遍DFS: 计算子树异或和, 构建子树内字典树t1
    void dfs1(int x, int fa) {
        s_below[x] = a[x];   // 初始化子树异或和为当前节点值
        t1[x] = 0;           // 初始化子树字典树
        for (int y : e[x]) { // 遍历子节点
            if (y != fa) {
                dfs1(y, x); // 递归处理子节点
                s_below[x] ^=
                    s_below[y]; // 子树异或和 = 自身值 ^ 子节点的子树异或和
                // 将子节点的异或值插入字典树, 并合并到当前节点的t1
                t1[x] = merge(t1[x], insert(t1[y], s_below[y]));
            }
        }
    }

    // 第二遍DFS: 构建父方向字典树t2(存储从父节点到根的异或信息)
    void dfs2(int x, int fa, int fa1) {
        if (fa1 != -1) { // 非根节点的父方向
            // 父方向异或值 = 总异或 ^ 父节点的子树异或和(排除当前子树)
            t2[x] = insert(t2[fa], s ^ s_below[fa]);
        } else
            t2[x] = 0; // 根节点无父方向, 字典树为空
        // 递归处理子节点
        for (int y : e[x])
            if (y != fa)
                dfs2(y, x, fa);
    }

    // 第三遍DFS: 构建前缀字典树t3(从根到当前节点的路径异或值)
    void dfs3(int x, int fa) {
        t3[x] = root; // 当前节点的前缀字典树为当前根节点(记录根到x的路径信息)
        for (int y : e[x]) // 先递归子节点
            if (y != fa)
                dfs3(y, x);
        // 将当前节点的子树异或值插入前缀字典树(更新根节点, 供后续节点使用)
        root = insert(root, s_below[x]);
    }

    // 第四遍DFS: 构建后缀字典树t4(从当前节点到叶的路径异或值)
    void dfs4(int x, int fa) {
        t4[x] = root; // 当前节点的后缀字典树为当前根节点(记录x到叶的路径信息)
        // 反向遍历子节点(保证后缀顺序)
        for (int i = e[x].size() - 1; i >= 0; --i) {
            int y = e[x][i];
            if (y != fa)
                dfs4(y, x);
        }
        // 将当前节点的子树异或值插入后缀字典树(更新根节点, 供后续节点使用)
        root = insert(root, s_below[x]);
    }

    // 核心查询函数: 在字典树中查找最优异或组合, 更新最小分数ans
    template <class Tnode> void solve(int x, int u, Tnode* root) {
        int v = s ^ u;  // v:另外两个组件的异或和(总异或 ^ 当前子树异或u)
        int d = msb(u); // d:u的最高有效位(用于优化查询)
        if (!exist(root))
            return; // 字典树为空, 直接返回

        // 情况1.1: ((A,B),C), C为有效组件, 枚举C并计算A、B的最优值
        for (int I = 1; I <= 1; ++I) { // 循环仅执行一次, 用于局部作用域隔离
            if (d == L - 1)
                break;              // 最高位超出范围, 跳过
            int i = L - 1, pre_dep; // i:当前位; pre_dep:前缀节点的深度
            Tnode *cur = root,
                  *pre = 0; // cur:当前遍历节点; pre:记录可能的C组件前缀

            // 从最高位向下遍历, 寻找可能的C组件
            for (; i > d; --i) {
                if (get(v, i)) { // v的第i位为1
                    if (exist(cur->l()))
                        pre = cur->l(),
                        pre_dep = i - 1; // 记录左子树(0)作为候选C
                    if (!exist(cur->r()))
                        break; // 右子树(1)不存在, 终止遍历
                    else
                        cur = cur->r(); // 继续遍历右子树
                } else {                // v的第i位为0
                    if (!exist(cur->l()))
                        break; // 左子树(0)不存在, 终止遍历
                    else
                        cur = cur->l(); // 继续遍历左子树
                }
            }

            // 特殊情况: A=B=C(差值为0, 直接更新答案)
            if (d == -1 && i == d) {
                ans = 0;
                return;
            }
            if (!exist(pre))
                break; // 无有效C组件, 跳过

            // 进一步筛选C组件的子树
            for (i = pre_dep; i > d; --i)
                pre = exist(pre->r()) ? pre->r() : pre->l();

            if (d == -1) { // u无有效位, 直接计算差值
                ans = min(ans, v - pre->v);
                break;
            }

            // 1.1.1: 查找A的最优值(最小化v - A)
            if (exist(pre->l()))
                ans = min(ans, v - pre->l()->max);
            // 1.1.2: 查找B的最优值(最小化v - (u^B))
            if (exist(pre->r())) {
                for (cur = pre->r(), i = d - 1; i >= 0;
                     --i) { // 从d-位遍历到最低位
                    if (get(u, i))
                        cur = exist(cur->l()) ? cur->l() : cur->r();
                    else
                        cur = exist(cur->r()) ? cur->r() : cur->l();
                }
                ans = min(ans, v - (u ^ cur->v));
            }
        }

        // 情况1.2: (A,(B,C)), A为有效组件, 枚举A并计算B、C的最优值
        for (int I = 1; I <= 1; ++I) { // 循环仅执行一次, 用于局部作用域隔离
            if (d == L - 1)
                break;              // 最高位超出范围, 跳过
            int i = L - 1, pre_dep; // i:当前位; pre_dep:前缀节点的深度
            Tnode *cur = root,
                  *pre = 0; // cur:当前遍历节点; pre:记录可能的A组件前缀

            // 从最高位向下遍历, 寻找可能的A组件
            for (; i > d; --i) {
                if (!get(v, i)) { // v的第i位为0
                    if (exist(cur->r()))
                        pre = cur->r(),
                        pre_dep = i - 1; // 记录右子树(1)作为候选A
                    if (!exist(cur->l()))
                        break; // 左子树(0)不存在, 终止遍历
                    else
                        cur = cur->l(); // 继续遍历左子树
                } else {                // v的第i位为1
                    if (!exist(cur->r()))
                        break; // 右子树(1)不存在, 终止遍历
                    else
                        cur = cur->r(); // 继续遍历右子树
                }
            }

            if (!exist(pre))
                break; // 无有效A组件, 跳过

            // 进一步筛选A组件的子树
            for (i = pre_dep; i > d; --i)
                pre = exist(pre->l()) ? pre->l() : pre->r();

            if (d == -1) { // u无有效位, 直接计算差值
                ans = min(ans, pre->v - v);
                break;
            }

            // 1.2.1: 查找C的最优值(最小化C - v)
            if (exist(pre->r()))
                ans = min(ans, pre->r()->min - v);
            // 1.2.2: 查找B的最优值(最小化(u^B) - v)
            if (exist(pre->l())) {
                for (cur = pre->l(), i = d - 1; i >= 0;
                     --i) { // 从d-1位遍历到最低位
                    if (get(u, i))
                        cur = exist(cur->r()) ? cur->r() : cur->l();
                    else
                        cur = exist(cur->l()) ? cur->l() : cur->r();
                }
                ans = min(ans, (u ^ cur->v) - v);
            }
        }

        // 情况1.3 & 1.4: 处理A&B或B&C组合的最优值
        for (int I = 1; I <= 1; ++I) { // 循环仅执行一次, 用于局部作用域隔离
            if (d == -1)
                break;         // u无有效位, 跳过
            int i = L - 1;     // 当前位
            Tnode* cur = root; // 当前遍历节点

            // 从最高位向下遍历, 定位到目标子树
            for (; i > d; --i) {
                if (get(v, i)) { // v的第i位为1
                    if (!exist(cur->r()))
                        break; // 右子树(1)不存在, 终止遍历
                    else
                        cur = cur->r(); // 继续遍历右子树
                } else {                // v的第i位为0
                    if (!exist(cur->l()))
                        break; // 左子树(0)不存在, 终止遍历
                    else
                        cur = cur->l(); // 继续遍历左子树
                }
            }

            if (i > d)
                break; // 未找到目标子树, 跳过

            // 情况1.3: ((A,B),C), A&B为有效组合, 枚举A
            if (!get(v, d)) {   // v的第d位为0
                cur = cur->l(); // 进入左子树
                if (!exist(cur) || cur->max < v)
                    break; // 子树无效, 跳过

                // 深入子树查找最优A
                for (i = d - 1; i >= 0; --i) {
                    if (get(v, i))
                        cur = cur->r();  // v的第i位为1, 进入右子树
                    else {               // v的第i位为0
                        if (get(u, i)) { // u的第i位为1
                            if (exist(cur->r())) {
                                cur = cur->r();
                                --i;
                                break;
                            } // 右子树存在, 跳转
                            else
                                cur = cur->l(); // 否则进入左子树
                        } else {                // u的第i位为0
                            if (exist(cur->l()) && cur->l()->max >= v)
                                cur = cur->l(); // 左子树有效, 进入
                            else {
                                cur = cur->r();
                                --i;
                                break;
                            } // 否则进入右子树并跳转
                        }
                    }
                }

                // 计算A对应的差值
                for (; i >= 0; --i) {
                    if (get(u, i))
                        cur = exist(cur->r()) ? cur->r() : cur->l();
                    else
                        cur = exist(cur->l()) ? cur->l() : cur->r();
                }
                ans = min(ans, (u ^ cur->v) - v);
            }

            // 情况1.4: (A,(B,C)), B&C为有效组合, 枚举C
            else {              // v的第d位为1
                cur = cur->r(); // 进入右子树
                if (!exist(cur) || cur->min > v)
                    break; // 子树无效, 跳过

                // 深入子树查找最优C
                for (i = d - 1; i >= 0; --i) {
                    if (!get(v, i))
                        cur = cur->l();  // v的第i位为0, 进入左子树
                    else {               // v的第i位为1
                        if (get(u, i)) { // u的第i位为1
                            if (exist(cur->l())) {
                                cur = cur->l();
                                --i;
                                break;
                            } // 左子树存在, 跳转
                            else
                                cur = cur->r(); // 否则进入右子树
                        } else {                // u的第i位为0
                            if (exist(cur->r()) && cur->r()->min <= v)
                                cur = cur->r(); // 右子树有效, 进入
                            else {
                                cur = cur->l();
                                --i;
                                break;
                            } // 否则进入左子树并跳转
                        }
                    }
                }

                // 计算C对应的差值
                for (; i >= 0; --i) {
                    if (get(u, i))
                        cur = exist(cur->l()) ? cur->l() : cur->r();
                    else
                        cur = exist(cur->r()) ? cur->r() : cur->l();
                }
                ans = min(ans, v - (u ^ cur->v));
            }
        }
    }

    // 计算下界(用于剪枝, 避免无效查询)
    int lb(int x) {
        int v = s ^ x, k = msb(v); // v:异或值; k:v的最高有效位
        if (k <= 0)
            return 0;                     // 最高位过小, 下界为0
        int l = msb(~v & ((1 << k) - 1)); // 计算v的最低有效位
        // 计算下界: 取两部分的最大值
        return max(l >= 0 ? 1 << l : 0, x & (1 << k)
                                            ? x & ((1 << k) - 1)
                                            : (1 << k) - (x & ((1 << k) - 1)));
    }

    // 主DFS: 遍历所有节点, 处理两种情况并查询最优解
    void dfs(int x, int fa) {
        // 先递归处理子节点
        for (int y : e[x])
            if (y != fa)
                dfs(y, x);

        // 情况1: 枚举当前节点子树内的异或值(使用t1字典树)
        if (lb(s ^ s_below[x]) < ans)
            solve(x, s_below[x], x ? t1[x] : 0);
        // 情况2: 枚举当前节点外的异或值(组合t2/t3/t4字典树)
        if (lb(s_below[x]) < ans)
            solve(x, s ^ s_below[x], newnode3(t2[x], t3[x], t4[x]));
    }

    // 主函数: 初始化并求解
    int minimumScore(vector<int>& _a, vector<vector<int>>& edges) {
        int n = _a.size();
        a = &_a[0];
        s = 0;
        p = Pool;
        p3 = Pool3;
        ans = inf; // 初始化变量
        // 计算总异或和, 清空邻接表
        for (int i = 0; i < n; ++i)
            s ^= a[i], e[i].clear();
        // 构建树的邻接表
        for (auto& e0 : edges) {
            int x = e0[0], y = e0[1];
            e[x].push_back(y);
            e[y].push_back(x);
        }

        // 预处理: 计算子树异或和及字典树
        dfs1(0, -1);
        // 预处理: 构建父方向字典树
        dfs2(0, -1, -1);
        // 预处理: 构建前缀字典树
        root = 0;
        dfs3(0, -1);
        // 预处理: 构建后缀字典树
        root = 0;
        dfs4(0, -1);

        // 主逻辑: 查询最优解
        dfs(0, -1);
        return ans;
    }
};